package org.alis.smallcc.queen;

/** 
* @ClassName: EightQueen 
* @Description: 八皇后问题
* @author: smallcc
*/
public class EightQueen {
	private int count=0;
	private int[] queen=new int[8];
	public static void main(String args[]) {
		EightQueen queen = new EightQueen();
    	queen.eightQueen(0);
    	System.out.println("总共有 " +queen.count+ " 摆放方法");
    	
    }
	private boolean isLegal(int currentRow,int currentColumn){
		//遍历前面几列
    	for(int preColumn=0;preColumn<currentColumn;preColumn++) {
    		int row = queen[preColumn];
    		//说明在子preColumn的低currentRow已经有了皇后
    		if(row==currentRow) {
    			return false;
    		}
    		
    	    //行与行的差值
            int rowDiff= Math.abs(row -currentRow);
          
            //列于列的差值
            int columnDiff =  Math.abs(currentColumn-preColumn);
            //说明斜线上有皇后
            if(rowDiff==columnDiff ){
                return false;
            }
    	}
    	
    	//说明（currentRow,currentColumn)可以摆放。
    	return true;
	}
	/** 
	* @Title: eightQueen 
	* @Description: 
	* @throws 
	*/
	private void eightQueen(int currentColumn) {
		// 此for循环是想尝试将皇后放在当前列的每一行
		for(int row=0;row<8;row++){
			// 判断当前列的row行是否可以放置皇后
			if(isLegal(row,currentColumn)){
				// 放置皇后
				queen[currentColumn]=row;
				if(currentColumn!=7){
					// 摆放下一个皇后
					eightQueen(currentColumn+1);
				}else{
					// 摆放成功脱离递归
					count++;
					printQueen();
				}
			}
		}
	}
	
	private void printQueen(){
		System.out.println("\n第"+count+"种解决方案");
		for(int y=0;y<8;y++){
			for(int x=0;x<8;x++){
				if(queen[y]==x){
					System.out.print("Q");
				}else{
					System.out.print("*");
				}
			}
			System.out.println();
		}
		
	}
}
